Bin packing with a minimum

62 views
Skip to first unread message

Charlie Swan

unread,
Feb 27, 2025, 3:56:52 AMFeb 27
to MiniZinc
Hello!

I'm working on a bin packing problem, and I'm wondering if there is an efficient way to specify a minimum capacity for bins when using the `bin_packing` function. Not all available bins must be used, but if a bin is used, its weight should be at least x. In specific terms, I'm looking for something like the following:

```

predicate bin_packing(int: c,

                      int: m,

                      array [$$I] of var $$B: bin,

                      array [$$I] of int: w)

Requires that each item i with weight w[i], be put into bin[i] such that the sum of the weights of the items in each non-zero weight bin is at least the minimum weight m but does not exceed the capacity c.
```

I know this doesn't exist (as far as I can tell), but is there an efficient way to achieve the same thing, perhaps using global constraints?

Thank you!

krzysztof....@gmail.com

unread,
Feb 27, 2025, 2:31:03 PMFeb 27
to MiniZinc
Did you try library constraint

predicate bin_packing_load(array [$$B] of var int: load, array [$$I] of var $$B: bin, array [$$I] of int: w)

If you define load >= m /\ load <= c it should solve youe problem, I think.

Charlie Swan

unread,
Feb 28, 2025, 1:58:28 AMFeb 28
to MiniZinc
Maybe a basic question, but how do I define load >= m /\ load <= c given load is an array?

krzysztof....@gmail.com

unread,
Feb 28, 2025, 1:07:31 PMFeb 28
to MiniZinc
Sorry, it was a shortcut. You can define it as

array[1..n] of var m..c: load;

or define

array[1..n] of var int load;
constraint
   forall (i in 1..n) (load[i] >= m /\ load[i] <= c)
Reply all
Reply to author
Forward
0 new messages